package com.gorkr.labuladong.data_struct;

/**
 * @author gorkr
 * @date 2022/05/31 10:43
 **/
public class M236LowestAncestorOfaBinaryTree {

    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }



    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

        return find(root,p,q);
    }

    // 找到p或q节点返回找到的节点
    public TreeNode find(TreeNode root, TreeNode p, TreeNode q){
        if(root==null){
            return null;
        }
        if(root.val==p.val || root.val==q.val){
            return root;
        }


        TreeNode left = find(root.left,p,q);
        TreeNode right = find(root.right,p,q);

        if(left!=null&& right!=null){
            return root;
        }
        return left!=null?left:right;
    }
}
    